package coloring.alg;

import static coloring.utils.Util.colorNumber;
import static coloring.utils.Util.containsColor;
import static coloring.utils.Util.reRepresentGraph;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.Graph;
import org.jgrapht.alg.NeighborIndex;

import coloring.MyDefaultEdge;
import coloring.vertex.Vertex;

/**
 * Class for greedy coloring iterated algorithm. Uses combination of two
 * heuristics: Increasing Size and Increasing Degree
 * 
 * @author Croaker
 * 
 */
public class GreedyColoring {

	/**
	 * Maximal number of unproductive iterations
	 */
	private final int maxNumberOfUnproductiveIterations;

	/**
	 * 
	 * @param numberOfUnproductiveIterations
	 *            - Maximal number of unproductive iterations
	 */
	public GreedyColoring(int numberOfUnproductiveIterations) {
		this.maxNumberOfUnproductiveIterations = numberOfUnproductiveIterations;
	}

	public GreedyColoring() {
		this.maxNumberOfUnproductiveIterations = 10;
	}

	/**
	 * Colors graph by iterated greedy algorithm
	 * 
	 * @param graph
	 * @return colored graph
	 */
	public Graph<Vertex, MyDefaultEdge> color(
			Graph<Vertex, MyDefaultEdge> graph, boolean genAddInf) {
		if (genAddInf) {
			return colorWithAdditionalInf(graph);
		} else {
			return colorWithoutAdditionalInf(graph);
		}
	}

	private Graph<Vertex, MyDefaultEdge> colorWithAdditionalInf(
			Graph<Vertex, MyDefaultEdge> graph) {
		// Creating index on vertices of graph
		NeighborIndex<Vertex, MyDefaultEdge> index = new NeighborIndex<Vertex, MyDefaultEdge>(
				graph);
		int numberOfRepeats = 1;
		int totalCounter = 0;
		int colorsNum = graph.edgeSet().size();
		int numberOfProductiveIterations = 0;
		graph = initialColoring(graph, index);
		System.out.println("Graph after first coloring: \n"
				+ reRepresentGraph(graph.toString()));
		System.out.println("Initial: colors: " + colorNumber(graph) + '\n');
		while (numberOfRepeats < maxNumberOfUnproductiveIterations) {
			System.out.print(totalCounter + " number of step");
			totalCounter++;
			if (numberOfRepeats % 2 == 0) {
				System.out.println(" (IncreasingSize) ");
				applyIteration(graph, index, getVerticesOrderedBySize(graph));
			} else {
				System.out.println(" (IncreasingDegree) ");
				applyIteration(graph, index,
						getVerticesOrderedBySubgraphDegree(graph));
			}
			System.out.println("colors: " + colorNumber(graph));
			System.out.println(reRepresentGraph(graph.toString()));
			System.out.println("---------------------------");
			if (colorsNum > colorNumber(graph)) {
				numberOfRepeats = 0;
				colorsNum = colorNumber(graph);
				numberOfProductiveIterations++;
			} else {
				numberOfRepeats++;
			}
		}
		System.out.println("Total number of iterations: " + totalCounter);
		System.out.println("Number of productive iterations: "
				+ numberOfProductiveIterations);

		return graph;
	}

	private Graph<Vertex, MyDefaultEdge> colorWithoutAdditionalInf(
			Graph<Vertex, MyDefaultEdge> graph) {
		// Creating index on vertices of graph
		NeighborIndex<Vertex, MyDefaultEdge> index = new NeighborIndex<Vertex, MyDefaultEdge>(
				graph);
		int numberOfRepeats = 1;
		int totalCounter = 0;
		int colorsNum = graph.edgeSet().size();
		int numberOfProductiveIterations = 0;

		graph = initialColoring(graph, index);
		while (numberOfRepeats < maxNumberOfUnproductiveIterations) {
			totalCounter++;
			if (numberOfRepeats % 2 == 0) {
				applyIteration(graph, index, getVerticesOrderedBySize(graph));
			} else {
				applyIteration(graph, index,
						getVerticesOrderedBySubgraphDegree(graph));
			}
			if (colorsNum > colorNumber(graph)) {
				numberOfRepeats = 0;
				numberOfProductiveIterations++;
				colorsNum = colorNumber(graph);
			} else {
				numberOfRepeats++;
			}
		}
		System.out.println("Total number of iterations: " + totalCounter);
		System.out.println("Number of productive iterations: "
				+ numberOfProductiveIterations);
		return graph;
	}

	/**
	 * Applies one iteration of algorithm to the graph.
	 * 
	 * @param graph
	 *            graph for coloring (default: it is colored by color number 0)
	 * @param index
	 *            index of vertices
	 * @param verList
	 *            ordered list of vertices to color
	 * @return
	 */
	private Graph<Vertex, MyDefaultEdge> applyIteration(
			Graph<Vertex, MyDefaultEdge> graph,
			NeighborIndex<Vertex, MyDefaultEdge> index, List<Vertex> verList) {

		for (int i = 0; i < verList.size(); i++) {
			Vertex vertex = verList.get(i);
			boolean reColored = false;
			int color = vertex.getColor();
			int j = i + 1;

			while ((j < verList.size() - 1) && color == vertex.getColor()) {
				color = verList.get(j).getColor();
				j++;
			}

			while ((j < verList.size()) && (!reColored)) {
				color = verList.get(j).getColor();
				if (!containsColor(index.neighborsOf(vertex), color)) {
					vertex.setColor(color);
					reColored = true;
				}
				j++;
			}
		}
		return graph;
	}

	/**
	 * Initial coloring of graph, without any heuristics
	 * 
	 * @param graph
	 * @param index
	 * @return
	 */
	private Graph<Vertex, MyDefaultEdge> initialColoring(
			Graph<Vertex, MyDefaultEdge> graph,
			NeighborIndex<Vertex, MyDefaultEdge> index) {
		List<Vertex> vertices = new ArrayList<Vertex>(graph.vertexSet());
		vertices.get(0).setColor(1);

		for (int i = 1; i < vertices.size(); i++) {
			boolean reColored = false;
			int color = 1;
			while (!reColored) {
				if (!containsColor(index.neighborsOf(vertices.get(i)), color)) {
					vertices.get(i).setColor(color);
					reColored = true;
				}
				color++;
			}
		}
		return graph;
	}

	/**
	 * Ordering vertex correspond to classes size(power) (by increasing)
	 * 
	 * @param graph
	 * @return list of ordered vertices
	 */
	private List<Vertex> getVerticesOrderedBySize(
			Graph<Vertex, MyDefaultEdge> graph) {
		int[] sizes = fillUpSizes(graph);

		List<Vertex> vertices = new ArrayList<Vertex>(graph.vertexSet());

		for (int i = 0; i < vertices.size(); i++) {
			for (int j = i; j < vertices.size(); j++) {
				if (sizes[vertices.get(j).getColor()] > sizes[vertices.get(i)
						.getColor()]) {
					Vertex tmp = vertices.get(i);
					vertices.set(i, vertices.get(j));
					vertices.set(j, tmp);
				}
			}
		}
		return vertices;
	}

	/**
	 * Ordering vertex correspond to classes total degree (by increasing)
	 * 
	 * @param graph
	 * @return list of ordered vertices
	 */
	// getVerticesOrderedBySize
	private List<Vertex> getVerticesOrderedBySubgraphDegree(
			Graph<Vertex, MyDefaultEdge> graph) {
		int[] sizes = fillUpDegrees(graph);

		List<Vertex> vertices = new ArrayList<Vertex>();
		for (Vertex vertex : graph.vertexSet()) {
			vertices.add(vertex);
		}

		for (int i = 0; i < vertices.size(); i++) {
			for (int j = i; j < vertices.size(); j++) {
				if (sizes[vertices.get(j).getColor()] > sizes[vertices.get(i)
						.getColor()]) {
					Vertex tmp = vertices.get(i);
					vertices.set(i, vertices.get(j));
					vertices.set(j, tmp);
				}
			}
		}
		return vertices;
	}

	/**
	 * Generates array where each cell contains number of vertex with such color
	 * in graph. (color number == cell position)
	 * 
	 * @param graph
	 * @return
	 */
	private int[] fillUpSizes(Graph<Vertex, MyDefaultEdge> graph) {
		int maxColorNumber = 0;
		for (Vertex vertex : graph.vertexSet()) {
			if (maxColorNumber < vertex.getColor()) {
				maxColorNumber = vertex.getColor();
			}
		}

		int[] sizes = new int[maxColorNumber + 1];

		for (Vertex vertex : graph.vertexSet()) {
			sizes[vertex.getColor()]++;
		}
		return sizes;
	}

	/**
	 * Generates array where each cell contains number of summary degree of
	 * class colored with color number N (N == color number == cell position)
	 * 
	 * @param graph
	 * @return
	 */
	private int[] fillUpDegrees(Graph<Vertex, MyDefaultEdge> graph) {
		int maxColorNumber = 0;
		for (Vertex vertex : graph.vertexSet()) {
			if (maxColorNumber < vertex.getColor()) {
				maxColorNumber = vertex.getColor();
			}
		}

		int[] sizes = new int[maxColorNumber + 1];

		for (Vertex vertex : graph.vertexSet()) {
			sizes[vertex.getColor()] += graph.edgesOf(vertex).size();
		}
		return sizes;
	}
}
